import java.util.LinkedList;
import java.util.Queue;

//图像渲染
//测试连接 https://leetcode.cn/problems/flood-fill/
public class FloodFill {
    //基于点(x,y) 表示上下左右方向各个点的坐标情况
    int[] dx = {-1,1,0,0};
    int[] dy = {0,0,-1,1};

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int start = image[sr][sc];
        if(start == color) return image;  //起点颜色和需要填充的是一样的

        int m = image.length, n = image[0].length;  //数组的行数和列数

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{sr,sc});  //将初始位置放入队列中

        while(!queue.isEmpty()) {
            int[] head = queue.poll();
            int a = head[0], b = head[1]; //获取队列中要进行颜色填充的图像

            image[a][b] = color; //填充颜色

            //向上下左右四个方向寻找符合要求的图像
            for(int i = 0; i < 4; i++) {
                int x = a + dx[i], y = b + dy[i];
                if(x >=0 && x < m && y >= 0 && y < n && image[x][y] == start) {
                    queue.add(new int[]{x,y});
                }
            }
        }

        return image;
    }
}
